The present invention relates to n-valued Linear Feedback Shift Registers (LFSRs). More specifically it relates to equivalency of n-valued LFSRs in Fibonacci and Galois configuration, implemented in binary circuitry.
Data scramblers, descramblers, sequence generators, detectors and coders based on shift registers with feedback are important components in data communications and data transfer in applications such as magnetic and optical data storage. It is known that linear feedback shift registers (LFSRs) can be realized in Fibonacci and Galois configurations. LFSRs in Fibonacci configuration are easier to analyze. Descramblers in Fibonacci are self-synchronizing. No prior art was found with sequence descramblers in a first Galois configuration. However descramblers in a first Galois configuration herein provided as an aspect of the present invention are not self-synchronizing. LFSRs in Galois configuration require fewer clock cycles for execution than Fibonacci equivalents.
LFSRs are also of interest in n-valued applications with n>2. It is sometimes advantageous to design an LFSR in Fibonacci configuration, while implementing it in Galois configuration. It may also be advantageous to implement an n-valued sequence generator in Galois configuration, because it is fast. One may want also to create a matching self synchronizing detector for such a generator, which may be in Fibonacci configuration. The rules for creating corresponding n-valued Fibonacci equivalent LFSRs in descramblers to Galois scramblers were not known prior to the present invention.
This invention relates to the processing of multi-valued or n-state (non-binary) signals with n>2. More in particular it relates to the scrambling, descrambling, generation and the detection of multi-valued (non-binary) or n-state signals representing sequences of multi-valued (non-binary) or n-state symbols such as n-valued pseudo-noise sequences. Multi-valued signals, also referred to as n-valued or n-state signals, can assume one of n states, wherein n is greater than or equal to three.
The n-state scramblers and descramblers are implemented by using a Linear Feedback Shift Register or LFSR. Well known is the binary LFSR based scrambler and the corresponding self synchronizing LFSR based binary descrambler.
Its potential application is in telecommunication systems, control systems and other applications. Specific examples of utility where the invention can be used include spread-spectrum technologies, signal scrambling, CDMA, line-coding including error control, error detection and error control coding and scrambling application in video, voice and data communication and other signal distribution.
LFSR based scramblers are used to change the appearance of a digital signal in such a way that during transmission the signal is different from the original signal. The original signal can be recovered from the scrambled signal at the receiving end by a descrambler. Most commonly in today's telecommunications, the scramblers relate to binary signals.
Scrambling of a binary signal can be achieved by combining the binary signal to be scrambled with a second known binary signal through a digital circuit that has the characteristics of a reversible function. A known signal is commonly known as a key and may for instance be derived from a prime number, which may be a large prime number.
In the case of scrambling with an LFSR scrambler there is no real known signal. A second signal that is used for scrambling comes from the LFSR. Such a signal is essentially unknown. However, the nature of the LFSR allows the signal from the LFSR to be reconstructed at the receiving side. Though the signal from the LFSR is still unknown, it can be reconstructed and thus can be applied to recover the original signal from a scrambled signal.
The inventor has provided the rule for an n-valued or n-state LFSR based descrambler corresponding to an n-valued LFSR based scrambler. This has been disclosed in U.S. patent application Ser. No. 10/935,960 filed Sep. 8, 2004 entitled Ternary and multi-valued digital signal scramblers, descramblers and sequence generators and in U.S. patent application Ser. No. 10/912,954 filed Aug. 6, 2004 entitled Ternary and higher multi-valued digital scramblers/descramblers, which are both incorporated herein by reference in their entirety.
There are two known binary functions that can perform this reversible function: the Exclusive Or (XOR) and the Equality function in a binary scrambler and descrambler. The XOR function is also known as the modulo-2 adding function.
Telecommunication markets such as wireless communications and Internet communications demonstrate an ongoing increase in demand for higher information transmission rates. This demand in increased information transmission rates in wireless communications is addressed by increasing bandwidth of communication channels, by compression of the information and by moving into much higher radio spectra (such as Ultra Wide Band in the 5 GHz area). Eventually, new technology has to be applied to obtain better performance from existing bandwidth, starting with highly congested spectrum areas. Current transmission technology predominantly uses digital binary signals. One possible technology to provide better bandwidth usage is the application of multi-valued or n-state signals on a much broader scale. Scrambling, descrambling and signal sequence generation is an important element of signal processing technology, especially in wireless communications. Currently very little technology exists that can perform multi-valued digital scrambling, descrambling and sequence generation. Most of existing solutions in scrambling, descrambling and sequence generation only performs binary functions, as previously discussed. Transmission of non-binary signals already takes place. Examples are for instance QAM-2p signals with p≧2. One may easily find articles describing QAM-4096 signals. A QAM-4096 symbol may capture the equivalence of 12 bits.
Despite the transmission of high information content signals, processing of symbols in general takes place completely in the binary domain. The processing of 2p valued or state signals may be facilitated by considering a 2p state signal as being defined in GF(2p). This allows the creation of GF(2p) based LFSRs as was described extensively by the inventor in U.S. patent application Ser. No. 12/137,945 filed on Jun. 12, 2008 which is incorporated herein by reference in its entirety. The application describes scramblers, descramblers and sequence generators.
The LFSR over GF(2p) approach may also be applied to other novel types of scramblers, sequence generators and sequence detectors which may provide for instance better security or a greater statistical variety in sequences and changing of sequences.
Accordingly, new and improved methods and apparatus for n-state scrambling, descrambling, sequence generation and sequence detection on multi-valued or n-state signals with binary technologies are required.